import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 1727. 重新排列后的最大子矩阵
 * https://leetcode-cn.com/problems/largest-submatrix-with-rearrangements/
 */
public class Solutions_1727 {
    public static void main(String[] args) {
        int[][] matrix1 = {{0, 0, 1}, {1, 1, 1}, {1, 0, 1}};  // output: 4
        int[][] matrix2 = {{1, 0, 1, 0, 1}};  // output: 3
        int[][] matrix3 = {{1, 1, 0}, {1, 0, 1}};  // output: 2
        int[][] matrix4 = {{0, 0}, {0, 0}};  // output: 0
        int[][] matrix5 = {{0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0},
                {0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1},
                {1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1},
                {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1},
                {1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0}};  // output: 75

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(matrix1);
        inputs.add(matrix2);
        inputs.add(matrix3);
        inputs.add(matrix4);
        inputs.add(matrix5);

        for (int i = 0; i < inputs.size(); i++) {
            int result = largestSubmatrix(inputs.get(i));
            System.out.println(result);
        }
    }

    /**
     * 解法二：排序-优化版（7ms）
     */
    public static int largestSubmatrix(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        for (int i = 1; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 1) {
                    // 当前数值为 1 时，那么高度累加
                    matrix[i][j] += matrix[i - 1][j];
                }
            }
        }
        int max = 0;

        // 对每行进行排序并计算
        for (int[] arr : matrix) {
            Arrays.sort(arr);
            for (int i = col - 1; i >= 0; i--) {
                int cur = arr[i] * (col - i);
                max = Math.max(max, cur);
            }
        }
        return max;
    }

    /**
     * 解法一：排序（17ms）
     */
    public static int largestSubmatrix2(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        int res = 0;
        // heights[0] = 9，表示遍历的当前行时，第 1 列的高度是 9
        int[] heights = new int[col];
        // 排序后，进行处理
        for (int i = 0; i < row; i++) {
            // 关键：对每一行都进行计算
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == 0) {
                    heights[j] = 0;
                } else {
                    // 累积高度
                    heights[j] ++;
                }
            }
            // 防止排序时改变 heights，所以传入的是 heights 的拷贝
            int curRowMax = getLargestSubmatrix(heights.clone());
            res = Math.max(res, curRowMax);
        }
        return res;
    }

    public static int getLargestSubmatrix(int[] arr) {
        int max = 0;
        Arrays.sort(arr);
        int len = arr.length;
        for (int i = len - 1; i >= 0; i--) {
            max = Math.max(max, arr[i] * (len - i));
        }
        return max;
    }
}
